package graph_algorithms;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */


import java.io.*;
import java.util.Vector;


public class Dijikstra{
	private Graph g;
	
	private double L[];
	private double Lu[];
	private int s;
	public int predecessor[];
	private Vector<Integer> PL;
	private Vector<Integer> TL;
	private int t;
	
	public Dijikstra(Graph g){
		this.g=g;
		L=new double[g.n];
		Lu=new double[g.n];
		s=0;t=g.n-1;
		PL=new Vector<Integer>();
		TL=new Vector<Integer>();
	}
	
	private void displaySolutionDSP(){
		int k=0;
		for(double i:L){
			System.out.print("Length of shortest path from "+s+" to "+k+" is "+i);
			System.out.println();
			k++;
		}
	}
	
	private void displayRoute(int v){
		if (v!=s){
			displayRoute(predecessor[v]);
			System.out.print("->"+v);
		}
		else{
			System.out.print(v);
		}
	}
	
	
	/*
	 * THIS FUNCTION ACTUALLY COMPUTES THE SHORTEST PATH TO ALL VERTICES FROM THE startVertex.
	 * FOLLOW predecessor[v] TO FIND THE SHORTEST ROUTE TO THE STARTING VERTEX.
	 */
	public void dijikstrasShortestPath(int startVertex, int terminalVertex){
		
			s=startVertex;
			t=terminalVertex;
		
		
		PL.add(s);
		L[s]=0;
		predecessor=new int[g.n];
		
		for(int i=0;i<g.n;i++){
			if (i!=s){
				TL.add(i);
				if (g.G[s][i]){
					Lu[i]=g.D[s][i];
					predecessor[i]=s;
				}
				else{
					Lu[i]=Double.MAX_VALUE;
					predecessor[i]=0;
				}
			}
		}
		auxDsp();
		//displaySolutionDSP();
		System.out.println("Shortest route from "+s+" to "+t+" is ");
		System.out.println();
		displayRoute(t);
	}
	
	private void auxDsp(){
		for(int v=0;v<g.n;v++){
		
			//TRANSFER THE CONTENTS OF TL (TEMPORARYLIST) TO I[].
			Integer I[]=new Integer[TL.size()];
			for(int i=0;i<TL.size();i++){
				I[i]=(Integer)TL.elementAt(i);
			}
			int k=0;
			double min=Double.MAX_VALUE;
			
			//ITERATE OVER I AND FIND THE MINIMUM IN I[].
			for(int i: I){
				if (min>Lu[i]){
					k=i;
					min=Lu[i];
				}
			}
			
			//NOW FOR SURE THE MINIMUM DISTANCE FROM THE START VERTEX TO THIS VERTEX k HAS BEEN FOUND.
			//SO IT CAN BE REMOVED FROM THE TEMPORARYLIST AND CAN BE ADDED TO THE PERMANENT LIST.
			L[k]=Lu[k];
			PL.add(k);
			TL.removeElement(k);
			
			for(int i=0;i<TL.size();i++){
				I[i]=(Integer)TL.elementAt(i);
			}
		
			for(int i:I){
				if (Lu[i]<=L[k]+g.D[i][k]){	
				}
				else{
					Lu[i]=L[k]+g.D[i][k];
					predecessor[i]=k;
				}	
			}			
		}
	}

}
